import javax.swing.tree.TreeNode;
import java.util.*;

class Solution1 {
    public static void reverse(int[] arr,int l,int r){
            while(l<r){
                int tmp = arr[l];
                arr[l] = arr[r];
                arr[r] = tmp;
                l++;
                r--;
            }
    }
    public void rotate(int[] nums, int k) {
        if(nums.length < 2 || nums == null || k == 0){
            return;
        }
         k = k % (nums.length);
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
    }

    public int minNumber0(int[] nums1, int[] nums2) {
        int x = 0;
        int y = 0;
        for (int i = 0; i < nums1.length; i++) {
            x |= 1<<nums1[i];
        }
        System.out.println(x);
        for (int m:nums2) {
            y |= 1<<m;
        }
        int ans = x & y;
        if (ans != 0){
            return count(ans);
        }
        x = count(x);
        y = count(y);
        return Math.min(x*10+y,y*10+x);
    }

    public static int count(int ans) {
        int count = 0;
       while (ans != 0){
           count++;
           ans >>=1;
       }
       return count;
    }

    public static void main(String[] args) {
        System.out.println(count(16));
        int[] a = {4,3,2};
        int x = 0;
        for (int i = 0; i < a.length; i++) {
            x |= 1<<a[i];
        }
        System.out.println(x);
        System.out.println(3 & 3);
        System.out.println(Integer.numberOfTrailingZeros(6));
    }
    /*
    位运算 2605. 从两个数字数组里生成最小数
     */
    public int minNumber2(int[] nums1, int[] nums2) {
        int mask1 = 0, mask2 = 0;
        //求出两个数组 每个元素在二进制中的位置
        //比如： 1 在二进制1下标的位置 01   2  -》 001
        for (int x : nums1) mask1 |= 1 << x;
        for (int x : nums2) mask2 |= 1 << x;
        //如果两个二进制有交集 则返回1在二进制的下标数
        int m = mask1 & mask2;
        //Integer.numberOfTrailingZeros 求二进制最右边1的所在下标数
        if (m > 0) return Integer.numberOfTrailingZeros(m);
        //拼接两个数组最小元素
        int x = Integer.numberOfTrailingZeros(mask1);
        int y = Integer.numberOfTrailingZeros(mask2);
        return Math.min(x * 10 + y, y * 10 + x);
    }
    public int minNumber1(int[] nums1, int[] nums2) {
            //从小到大排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        HashSet<Integer> set = new HashSet<>();
        for (int x : nums1) {
            set.add(x);
        }
        //找到两个数组相同的最小值
        //两数组最大元素不超过9
      int   minNum = 10;
        for(int m : nums2){
            if (set.contains(m)){
                if (m < minNum){
                    minNum = m;
                }
            }
        }
        if (minNum < 10){
            return minNum;
        }else{
            return  Math.min(nums1[0]*10+nums2[0],nums2[0]*10+nums1[0]);
        }
    }
    public int[] levelOrder(TreeNode root) {
        if(root == null){
            return new int[0];
        }
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> q =new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()){
            TreeNode cur = q.poll();
            int[] ret = new int[q.size()];
            list.add(cur.val);
            if (cur.left != null){
                q.offer(cur.left);
            }
            if (cur.right != null){
                q.offer(cur.right);
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }
//JZ6 从尾到头打印链表
    ArrayList<Integer> ans = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode == null)
            return new ArrayList<>();
        int ret = listNode.val;
        printListFromTailToHead(listNode.next);
        ans.add(ret);
        return ans;
    }
//JZ24 反转链表
    public ListNode ReverseList(ListNode head) {
        if (head == null)
            return null;
        //采用头插法
        ListNode cur = head.next;
        head.next = null;
        while (cur != null){
            //提前记录下一个节点
            ListNode curNext = cur.next;
            //头插
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

//JZ25 合并两个排序的链表
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        if (pHead1 == null)
            return pHead2;
        if (pHead2 == null)
            return pHead1;
        //设置虚拟节点
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (pHead1 != null && pHead2 != null){
            if (pHead1 != null && pHead1.val < pHead2.val){
                cur.next = pHead1;
                pHead1 = pHead1.next;
                cur = cur.next;
            }else {
                cur.next = pHead2;
                pHead2 = pHead2.next;
                cur = cur.next;
            }
        }
        if (pHead1 != null){
            cur.next = pHead1;
        }else {
            cur.next = pHead2;
        }
        return head.next;
    }
    public ListNode Merge1 (ListNode pHead1, ListNode pHead2) {
        // write code here
        if (pHead1 == null){
            return pHead2;
        }
        if (pHead2 == null){
            return  pHead1;
        }

        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (pHead1 != null && pHead2 != null){
            if (pHead1.val < pHead2.val){
                cur.next = pHead1;
                pHead1 = pHead1.next;
            }else{
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }
            cur = cur.next;
        }
        if (pHead1 != null){
            cur.next = pHead1;
        }else{
            cur.next = pHead2;
        }
        return head.next;
    }

    //JZ22 链表中倒数最后k个结点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        // write code here
        if(pHead == null || k <= 0){
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        //fast先走k步
        while (k > 0){
            //如果链表长度少于k 直接返回
            if (fast == null){
                return null;
            }
            fast = fast.next;
            k--;
        }
        //fast和slow一起走，最后slow就是倒数第k个节点
        while (fast != null ){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;

    }

    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode fast = head.next;//先走一步，防止只有两个节点
        ListNode slow = head;
        //1.找到中点节点
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //2.从中间节点断开，分成两个链表
        ListNode tmp = slow.next;//提前记录右边链表的头
        slow.next = null;
        //3.递归排序
        ListNode left = sortInList(head);
        ListNode right = sortInList(tmp);
        //4.合并两个链表
        ListNode newHead = new ListNode(-1);
        ListNode res = newHead;
        while (left != null && right!=null){
            if (left.val < right.val){
                res.next = left;
                left = left.next;
            }else {
                res.next = right;
                right = right.next;
            }
            res = res.next;
        }
        //5.判断哪个链表不为空
        res.next = left != null ? left : right;
        return newHead.next;
    }

    public ListNode deleteNode (ListNode head, int val) {
        // write code here 1 2 3 9 5 6
        if (head == null) return head;
        ListNode res =new ListNode(0);
        res.next = head;
        ListNode cur = head;
        ListNode prev = res;
        while (cur != null ){
            if (cur.val == val){
                prev.next =cur.next;
                break;
            }
            prev = cur;
            cur = cur.next;
        }
        return res.next;
    }
    public int Fibonacci (int n) {
        // write code here
        int f0 = 0;
        int f1 = 1;
        int f2 = f0+f1;
        while(n-2 >0){
            f0 = f1;
            f1 = f2;
            f2 = f0+f1;
            n--;
        }
        return f2;
    }
    public int jumpFloor (int number) {
        // write code here
        if(number <= 2){
            return number;
        }
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
}